# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/19 19:55
@FileName      : 01背包.py
@LastEditors   : None
@Editors       : PyCharm
"""
import numpy as np

N = 6  # 商品种类
weight = 12  # 背包容量
wares = [0, 1, 2, 3, 4, 5, 6]
prices = [0, 1, 5, 10, 20, 50, 100]


def knapsack01(w, p, N, W):
    knapsacks = np.zeros((W + 1, N + 1))
    for n in range(N + 1):
        for k in range(len(knapsacks)):
            if k >= w[n]:
                knapsacks[k][n] = p[n] + knapsacks[k - w[n]][n - 1]
            if knapsacks[k][n] < knapsacks[k][n - 1]:
                knapsacks[k][n] = knapsacks[k][n - 1]
    return knapsacks


knapsacks = knapsack01(wares, prices, N, weight)
result = knapsacks[weight][N]
print("该背包可容纳最大重量为 %d ,最大收益为 %d 。" % (weight, result))
# 追溯选中的商品
n = N
w = weight
print('所选商品为：')
while n > 0:
    # 如果在指定承重下，该商品对应的收益和上一个商品对应的收益相同，则表明未选中
    if knapsacks[w][n] == knapsacks[w][n - 1]:
        n -= 1
    else:
        w -= wares[n]
        print("(%d,%d)" % (wares[n], prices[n]))
        n -= 1
